import java.util.Arrays;

// 基数排序
// 测试链接 : https://leetcode.cn/problems/sort-an-array/
public class Code02_RadixSort {

    // 可以设置进制，不一定10进制，随你设置
    public static int BASE = 10;
    public static int MAXN = 50001;
    // 辅助数组，用于在基数排序过程中临时存储数据
    public static int[] help = new int[MAXN];
    // 用于计数每个数位上数字出现的次数，数组大小为进制数BASE
    public static int[] cnts = new int[BASE];

    // 对输入数组进行排序并返回排序后的数组
    public static int[] sortArray(int[] arr) {
        // 如果数组长度大于1才需要排序
        if (arr.length > 1) {
            // 如果会溢出，那么要改用long类型数组来排序

            // 获取数组的长度
            int n = arr.length;

            // 找到数组中的最小值
            int min = arr[0];
            for (int i = 1; i < n; i++) {
                min = Math.min(min, arr[i]);
            }

            int max = 0;
            for (int i = 0; i < n; i++) {
                // 数组中的每个数字，减去数组中的最小值，就把arr转成了非负数组
                // 这样做是为了在基数排序中更方便地处理数字，避免出现负数情况
                arr[i] -= min;
                // 记录数组中的最大值，这是为了确定基数排序的轮数
                max = Math.max(max, arr[i]);
            }

            // 根据最大值在BASE进制下的位数，决定基数排序做多少轮
            radixSort(arr, n, bits(max));

            // 数组中所有数都减去了最小值，所以最后不要忘了还原
            for (int i = 0; i < n; i++) {
                arr[i] += min;
            }
        }
        // 返回排序后的数组（如果原数组长度为0或1，直接返回原数组）
        return arr;
    }

    // 返回number在BASE进制下有几位
    public static int bits(int number) {
        int ans = 0;
        // 通过不断除以进制数BASE，直到number为0，计算出number在BASE进制下的位数
        while (number > 0) {
            ans++;
            number /= BASE;
        }
        return ans;
    }

    // 基数排序核心代码
    // arr内要保证没有负数
    // n是arr的长度
    // bits是arr中最大值在BASE进制下有几位
    public static void radixSort(int[] arr, int n, int bits) {
        // 理解的时候可以假设BASE = 10
        // 针对每一位进行基数排序，从最低位开始，逐步向高位排序
        for (int offset = 1; bits > 0; offset *= BASE, bits--) {
            // 每次对新的一位进行排序时，先将计数数组清零
            Arrays.fill(cnts, 0);

            // 统计每个数字在当前位（由offset决定）上的数字出现的次数
            for (int i = 0; i < n; i++) {
                // 数字提取某一位的技巧
                // 通过将数字除以offset并取余数得到当前位上的数字，然后在计数数组中相应位置加1
                cnts[(arr[i] / offset) % BASE]++;
            }

            // 将计数数组转换为前缀和数组，这样可以确定每个数字在排序后的位置范围
            for (int i = 1; i < BASE; i++) {
                cnts[i] = cnts[i] + cnts[i - 1];
            }

            // 从数组末尾开始，根据当前位的计数将数字放入辅助数组help中正确的位置
            for (int i = n - 1; i >= 0; i--) {
                // 前缀数量分区的技巧
                // 数字提取某一位的技巧
                // 根据当前位的数字在计数数组中的位置，将数字放入辅助数组help中相应的位置
                // 同时将计数数组中对应位置减1，表示已经处理了一个该数字
                help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
            }

            // 将辅助数组help中的元素复制回原数组arr，完成当前位的排序
            for (int i = 0; i < n; i++) {
                arr[i] = help[i];
            }
        }
    }
}